The covariance matrix adaptation evolution strategy (CMA-ES) is arguably one of the most powerful real-valued derivative-free optimization algorithms, finding many applications in machine learning. The CMA-ES is a Monte Carlo method, sampling from a sequence of multi-variate Gaussian distributions. Given the function values at the sampled points, updating and storing the covariance matrix dominates the time and space complexity in each iteration of the algorithm. We propose a numerically stable quadratic-time covariance matrix update scheme with minimal memory requirements based on maintaining triangular Cholesky factors. This requires a modification of the cumulative step-size adaption (CSA) mechanism in the CMA-ES, in which we replace the inverse of the square root of the covariance matrix by the inverse of the triangular Cholesky factor. Because the triangular Cholesky factor changes smoothly with the matrix square root, this modification does not change the behavior of the CMA-ES in terms of required objective function evaluations as verified empirically. Thus, the described algorithm can and should replace the standard CMA-ES if updating and storing the covariance matrix matters.

This paper makes a solid contribution to speeding up the celebrated CMA-ES algorithm which is arguably the best algorithm for non-convex black-box optimization when little is known about the topology of the objective function and first or higher-order information is difficult to access or not helpful. The proposed method speeds up the algorithm considerably and shows no deterioration of optimization performance on the synthetic test cases. Although this is of general importance, one weak point of ANY speed-up proposal for CMA-ES is that, in practice, the overall optimization process is dominated by the runtime of the black-box oracle (the objective function), and, often, the actual runtime of the CMA-ES is negligible compared to that. In addition, in typical scenarios where CMA-ES is used, the dimensionality of the problems does not go beyond a few tens of variables. Only in the case where a single function evaluation is on the order of milliseconds or smaller and the dimensionality is higher, the runtime of CMA-ES plays an important role, and this is targeted scenario here (which may be less realistic in practice).

The covariance matrix adaptation evolution strategy (CMA-ES) is arguably one of the most powerful real-valued derivative-free optimization algorithms, finding many applications in machine learning. The CMA-ES is a Monte Carlo method, sampling from a sequence of multi-variate Gaussian distributions. Given the function values at the sampled points, updating and storing the covariance matrix dominates the time and space complexity in each iteration of the algorithm. We propose a numerically stable quadratic-time covariance matrix update scheme with minimal memory requirements based on maintaining triangular Cholesky factors. This requires a modification of the cumulative step-size adaption (CSA) mechanism in the CMA-ES, in which we replace the inverse of the square root of the covariance matrix by the inverse of the triangular Cholesky factor.